package demo.practice.competition;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class P5816_2 {

    public int[] maxGeneticDifference(int[] parents, int[][] queries) {
        //构造一棵树，维护 父->一堆孩子的关系
        Map<Integer, List<Integer>> tree = new HashMap<>();
        for (int i = 0; i < parents.length; ++i) {
            if (!tree.containsKey(parents[i])) {
                tree.put(parents[i], new ArrayList<>());
            }
            tree.get(parents[i]).add(i);
        }

        //构造查询map    node->queryVal -> res   res先写0
        Map<Integer, Map<Integer, Integer>> queryMap = new HashMap<>();
        for (int i = 0; i < queries.length; ++i) {
            if (!queryMap.containsKey(queries[i][0])) {
                queryMap.put(queries[i][0], new HashMap<>());
            }
            queryMap.get(queries[i][0]).put(queries[i][1], 0);
        }


        //从root开始dfs
        dfs(new ZeroOneTrie(), tree, queryMap, tree.get(-1).get(0));

        //把结果拼出来
        int[] r = new int[queries.length];
        for (int i = 0; i < r.length; ++i) {
            r[i] = queryMap.get(queries[i][0]).get(queries[i][1]);
        }
        return r;
    }


    private void dfs(ZeroOneTrie zeroOneTrie, Map<Integer, List<Integer>> tree,
                     Map<Integer, Map<Integer, Integer>> queryMap, int root) {
        //把这个节点加入0-1字典树
        zeroOneTrie.insert(root);

        //做完root对应的查询
        if (queryMap.containsKey(root)) {
            Map<Integer, Integer> resMap = queryMap.get(root);
            for (Integer query : resMap.keySet()) {
                resMap.put(query, query ^ zeroOneTrie.queryMax(query));
            }
        }

        //下一层
        if (tree.containsKey(root)) {
            List<Integer> next = tree.get(root);
            for (int r : next) {
                dfs(zeroOneTrie, tree, queryMap, r);
            }
        }
        // 回溯
        zeroOneTrie.delete(root);
    }
}

class ZeroOneTrie {
    Node root = new Node();

    /**
     * 按二进制从高到低插入
     *
     * @param num
     */
    public void insert(int num) {
        Node cur = root;
        for (int i = 31; i >= 0; --i) {
            int op = ((num >> i) & 1);
            if (cur.next[op] == null) {
                cur.next[op] = new Node();
            }
            cur = cur.next[op];
            cur.count++;
        }
        cur.val = num;
    }

    public void delete(int num) {
        Node cur = root;
        for (int i = 31; i >= 0; --i) {
            int op = ((num >> i) & 1);
            if (cur.next[op].count == 1) {
                cur.next[op] = null;
                return;
            } else {
                cur = cur.next[op];
                cur.count--;
            }
        }
    }

    /**
     * 查询所有数中和num异或结果最大的数
     *
     * @return
     */
    public int queryMax(int num) {
        Node cur = root;
        for (int i = 31; i >= 0; --i) {
            int op = ((num >> i) & 1) == 0 ? 1 : 0;
            if (cur.next[op] != null) {
                cur = cur.next[op];
            } else {
                op = op ^ 1;
                cur = cur.next[op];
            }
        }
        return cur.val;
    }

    public int queryMin(int num) {
        Node cur = root;
        for (int i = 31; i >= 0; --i) {
            int op = ((num >> i) & 1);
            if (cur.next[op] != null) {
                cur = cur.next[op];
            } else {
                cur = cur.next[op ^ 1];
            }
        }
        return cur.val;
    }

    private class Node {
        public int count = 0;
        public int val = 0;
        public Node[] next = new Node[2];
    }
}
